package mo.leetcode_hot;

import java.util.HashMap;
import java.util.Map;

public class L146 {

    private Map<Integer, Node> map = new HashMap<>();

    private int capacity;
    private int used;
    private Node head;
    private Node tail;

    public L146(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            node.pre.next = node.next;
            node.next.pre = node.pre;
            head.next.pre = node;
            node.next = head.next;
            head.next = node;
            node.pre = head;
            return;
        }
        Node node = new Node(key, value);
        if (used == capacity) {
            Node removed = tail.pre;
            removed.pre.next = removed.next;
            removed.next.pre = removed.pre;
            map.remove(removed.key);
        } else {
            used++;
        }
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
        map.put(key, node);
    }

    private class Node {
        private Node pre;
        private Node next;
        private int key;
        private int value;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

    }

}
